A system configured to improve the availability or the like by holding data in a distributed state in a plurality of nodes which are connected with one another over a network has been proposed and may be called a distributed data store.
FIG. 1 illustrates an exemplary system configuration of a distributed data store. An exemplary process which is performed when the distributed data store has received a distributed transaction will be discussed with reference to FIG. 1. For example, a distributed framework 12 in a node NODE_B receives a request for execution of a distributed transaction including operation information specifying an operation. In the example illustrated in FIG. 1, it is supposed that the distributed framework 12 has received operation information specifying an operation “Get(DATA_A1)” (that is, an operation of acquiring a value of data DATA_A1). Then, the distributed framework 12 in the NODE_B locates, by using a distributed hash table (DHT) or the like, a node that holds data to be operated in the operation. Although, in the case that plural pieces of operation information corresponding to a plurality of operations are included in the request for execution of the distributed transaction, a plurality of nodes may be located in some cases, in the example illustrated in FIG. 1, it is supposed that only a node NODE_A has been located. In the above mentioned situation, the distributed framework 12 in the NODE_B forwards the operation information to a distributed framework 11 in the NODE_A. The distributed framework 11 in the NODE_A that has received the operation information from the NODE_B executes the operation (that is, the distributed framework 11 acquires the value of the DATA_A1). In addition, the distributed framework 11 in the NODE_A sends the acquired value of the DATA_A1 to the NODE_B. The distributed framework 12 in the NODE_B that has received the value of the DATA_A1 from the NODE_A sends the received value of the DATA_A1 to a client terminal.
In a distributed data store as mentioned above, each of the plurality of nodes may possibly receive a request for execution of a distributed transaction. Each node does not perform serialization of the transactions upon receipt of the request for execution thereof but does later in accordance with timestamps or the like.
In a distributed data store as mentioned above, the node (hereinafter, referred to as a receptor) that has received the request for execution of the distributed transaction may not always happen to be the node (hereinafter referred to as a container) that holds the data to be operated in the operation. Therefore, it may sometimes occur that operations are executed in the order different from the order in which the operations are originally to be executed, in the case that a timing at which operation information specifying a specific operation reaches the container is delayed owing to, for example, a delay in communication between nodes. In a distributed data store of the type that a plurality of nodes hold replicas of data, when a delay has occurred in timing at which each of the replicas is synchronized with the data, it may sometimes occur that an operation which is to be executed originally after the synchronization is executed before the synchronization.
When operations are executed in the order different from the original correct order of execution, the following problems may occur. For example, it is supposed that a first operation is to set “2” to certain specific data, a second operation is to add “3” to the specific data, and a third operation is to multiply “4” to the specific data. In the above mentioned case, when the operations are executed in the original order, “20” will be obtained as an ultimate execution result of the operations. However, if the first and second operations are executed in reverse order, “11” will be obtained as an ultimate execution result of the operations. That is, when such operations that an ultimate execution result thereof depends on the order of execution are executed on data stored in the distributed data store, a correct execution result of the operations may not be obtained in some cases. Accordingly, such a problem may arise that it is difficult to apply operations to data stored in the distributed data store unless the operations are of the type that the ultimate execution result thereof does not depend on the order of execution of the operations (for example, operations of setting an immediate value and operations of acquiring a value of data).
It is said that a theorem called the CAP theorem is true in a system which performs a process by using a plurality of nodes in a distributed state, for example, a distributed data store as mentioned above. The CAP theorem states that it is impossible for a distributed system to simultaneously provide consistency of data, availability of a system, and tolerance to network partitions. In a distributed data store as mentioned above, availability of a system and tolerance to network partitions are features to be preferentially provided and hence it may sometimes occur that a system is constructed in a state in which strictness to consistency of data is loosened. As a result, such a situation may sometimes occur that data before update is temporarily presented to a user. In many cases, there will be no problem, for example, in written contents of a large-scale bulletin board, goods explanation pages of a shopping site and the like even when such a situation as mentioned above has temporarily occurred. A way of thinking that “although consistency of data is not established at a certain point of time, all is well as long as consistency of data is finally established” may be sometimes called an eventual consistency.
As a technique relating to a distributed data store, a technique as follows is proposed. Specifically, replicas of data are held in a plurality of nodes and a change in the data is reflected on the replicas in background, thereby ensuring the availability of the system. When a conflict is found in the data, a process for resolving the conflict is performed on the side of an application process upon data reading.
The thesis titled “Dynamo: Amazon's Highly Available Key value Store” by G. DeCandia et al. discloses a related technique.